The architecture of a typical, single-processor computing system can be viewed as some variation of the von Neumann model of computation. According to this model, instructions and data are stored in the same memory, and the processor fetches instructions one by one from the memory, executing operations on data as specified in the instructions. As the speed of processors has increased, there has been a need to find ways to more suitably match the access time of the main computer memory to the computational speed of the processor. One known way of accomplishing this is through the use of cache memory which typically has a much faster access time than main memory, but can also be many times more expensive than main memory. Accordingly, as a practical consideration, it is usually much smaller than main memory.
A cache memory contains some subset of the information stored in main memory, and resides between the processing unit and the system bus, which provides the data path between a processor and main memory. When a processor attempts to access a main memory location that is copied in its cache (a cache `hit`), no access to main memory is required to provide the requested value to the CPU, and the processor can resume operation more quickly. On the other hand, when the processor attempts to access a main memory location that is not copied in the cache (a cache `miss`), a main memory access must occur. In this event the read data is sent to both the processor and to the cache, so that some subsequent attempts to access the memory location will result in cache hits. In this way, the effective memory access time for the processor is reduced to a value somewhere between the fast access time of the cache memory and the slower access time of main memory. Since the cache memory is usually smaller than main memory by an order of magnitude or more, the computer subsystem which controls the cache memory must employ methods of determining which memory location is to correspond to which cache location (the mapping function), and which cache location should be overwritten in the case that a new memory location is to be written into an already full cache (the cache replacement algorithm). Judicious selection of these configuration options can result in a cache `hit ratio` (the percentage of memory access requests that result in cache hits) of 90 to 99 percent.
Another critical aspect of cache performance is the procedure that must be followed in order for a processing unit to determine whether a desired memory location is also resident in that processing unit's cache memory. Many techniques in the art exist for allowing these cache memory look-ups to be as fast and efficient as possible. The exact technique employed depends upon the particular implementation of the cache itself, especially the mapping function. Typically, however, a structure called a `tag directory` or `tag store` is provided to enable swift cache look-ups. A tag store is a table of multiple entries, each entry corresponding to a block of a cache memory. Traditionally, a cache block contains several main memory words, and all access to the cache is performed in units of this basic cache block size. Each tag store entry contains enough bits to specify any one of the cache blocks in the cache. When a block of data from main memory is mapped into a cache block, the tag store entry corresponding to that cache block is loaded with the higher order bits of the address of the data block in main memory. In fully associative cache designs, when the processor wants to search the cache looking for a desired main memory location, it compares the desired address to the entries in the tag store. If a match is found, the corresponding word is selected from within the multiple word cache block. In a direct mapped cache design, the least significant bits of the address of interest are used as an index into the tag store. The remaining higher order bits of the address are then compared with the tag store entries to determine a cache hit. In a set associative cache design, the least significant bits of the address of interest are used as an index into a small number (e.g. 2 or 4) of locations within the tag store, the indexed entries from each of these locations is extracted and a comparison is performed on each of this limited number of entries in parallel to determine a cache hit.
A further enhancement that is useful for decreasing the average memory access time for a CPU module is to organize the cache memory in a multi-level hierarchical structure, with the smallest and fastest primary cache memory closest to the CPU, and increasingly slower and larger secondary cache memories along the data path between a processor and main memory. Such a configuration represents a compromise between the high cost of very fast memory devices and the slower access times of relatively lower cost memory devices. A cache miss in the fastest and smallest primary cache memory causes the CPU to access the next lower cache memory in the hierarchy, where the larger size suggests an even greater probability of a cache hit. A cache miss here causes the CPU to access a secondary cache memory even lower in the hierarchy, and so on, until such time as a cache hit occurs in some level of the cache structure, or a main memory access is initiated.
Along with the increase in system efficiency resulting from the use of cache memory, however, comes the problem of data coherence. That is, there must be assurance that a cache location holds the same value as the main memory location to which it corresponds. One way to maintain data coherence is to write modified values of data contained in the cache memory both to the cache memory (if it is resident in the cache) and to the corresponding main memory location, each time memory write access to that location is requested. This method is called a "no write-allocate" write-through policy. A write-through policy may alternatively allocate a memory location for write transactions for which the memory location is not already resident in its cache, in which case the write-through policy uses a write-allocate capability. Another cache coherence technique involves a write-back policy, in which a modified data value is not written to the slower main memory until the corresponding cache location must be overwritten. The tradeoff between these policies involves the requirement of greater bandwidth at the memory subsystem level in updating main memory for each write access in a write-through policy versus the increased complexity in cache coherence in a write-back policy. In systems with sufficient bandwidth, a write-through policy is often preferred due to its simplicity.
Recent decreases in the cost of processing units have facilitated the advent of a more radical departure from the von Neumann machine organization, in which a plurality of processors operate concurrently with each other, while still accessing a common main memory space via a common system bus. Each processor can have its own private cache which resides between the processor and the system bus. For such multi-processor systems, the use of cache memories is more crucial to system performance than in single processor systems, since each of the processors is in contention with the others for use of the common system bus in order to access the shared memory. The problem of data coherence is likewise more pronounced, since the value stored in a single memory location might at one time be replicated in the private cache memory of any or all of the processors. If the local cache memories each employs a write-back policy, the system must somehow ensure that when one processor modifies the value of a memory location and writes that modification only to its cache memory, the copies of that memory location in any of the other local caches reflects the change made by that one processor.
The present invention is directed to a multi-processor computer system comprising a plurality of CPU modules which share a common memory space via a time-shared system bus. The common memory space can be realized as a plurality of memory modules each containing part of the shared system memory. A CPU module includes a processor on which instructions are executed, a private cache memory unit and possibly additional supporting hardware for efficient control of the CPU module and coordination of the CPU module with other components of the system.
As is common in the art of multi-processor systems, any of the modules interfaced to the system bus can initiate one of four kinds of transactions on the bus: null, read, write and read data transactions. The time during which one of these transactions is taking place on the bus is called a bus cycle. A null transaction occurs when no module requires the bus, and is ignored by all modules. A read transaction is one in which a CPU sends a request to a memory module to return memory data. A write transaction is one in which a CPU sends a request to a memory module to write new memory data. A read data transaction is one in which a memory module returns data to a CPU module in response to a previous read transaction. Contention for use of system bus among the various modules is arbitrated in some manner specific to the system bus implementation and known in the art of arbitration protocols.
As part of the support hardware associated with a CPU module, known techniques in the art suggest that a structure called a Read Data Queue may be introduced between the system bus and the CPU module. This structure holds data values that have been returned from memory in response to read transactions. The queuing of read data enhances the performance of the system by allowing a processor to accomplish other tasks while main memory access is made, instead of waiting idly for the data to be returned. The Read Data Queue is a first-in-first-out (FIFO) queue containing multiple entries, each of which includes a data field and a valid bit. When the CPU module receives data from main memory via a read data transaction, that data is placed on one end of the Read Data Queue, and the valid bit is set for that entry. When the CPU is ready to accept incoming data to put in its cache memory, the first valid entry is removed from the other end of the queue and the valid bit is cleared.
Another FIFO structure called an Invalidate Queue may also be introduced between the system bus and the CPU module. The Invalidate Queue also contains multiple entries called `invalidates`, each including at least an address field and a valid bit. The CPU monitors the system bus for coherence transactions. In a system employing a write-through policy, the CPU module monitors for write transactions on the system bus. When any data write transaction is detected on the system bus, the address of that transaction is placed on one end of the CPU module's Invalidate Queue and the valid bit is set. When the CPU is able to process an invalidate, the first valid entry is removed from the other end of the Invalidate Queue and its valid bit is cleared. The address of the write transaction is checked against the contents of the cache structure, and if present, the entry corresponding to that address is marked as invalid. In this way, the CPU can be prevented from using data values which are outdated.
The requirements for cache coherency in multi-processor systems are complex. One component of cache coherency in multi-processor systems is maintained when each cache memory processes transactions in the same order as they occurred on the system bus. The order of invalidates as they appeared on the system bus can be preserved by the FIFO queue that holds them. Similarly, the order of read data transactions can be preserved in their FIFO queue. Unfortunately, however, the order of invalidates in relation to read data transactions, or equivalently, the order of read data transactions relative to invalidates, as they appeared on the system bus, is normally not preserved by the use of separate Read Data and Invalidate Queues
Alternative methods of maintaining cache coherence, which do not involve the use of the queues described above, also exist in the art. For example, the system could include additional hardware providing the means for direct communication between individual processor modules; or, the CPU's instruction set could include commands dedicated to preserving data coherency; or, means of direct communication could be established between main memory and each individual private cache memory. Another alternative would be to implement a global directory such that the system keeps track of what data is in each of the cache memories, allowing the system to invalidate data in a cache memory as required to maintain data coherence.
In implementing any of the above techniques, however, some expense is likely to be incurred, either in system cost or system performance. In the case of establishing paths of communication between processors or between cache memories and main memory, as well as in the case of including a global cache directory, this penalty would be primarily economic, while a modified instruction set would probably preserve data coherence at the expense of system performance.
Other systems which process every write transaction detected in order to preserve data coherence may suffer CPU (processor) bus saturation; that is, the servicing of invalidates by each CPU for every write transaction on the system bus would occupy a large amount of the multi-processor system's total computational time.
It would therefore be advantageous to implement an efficient means by which the number of invalidates propagated onto a private processor bus be "filtered", such that the processor bus not be overloaded. That is, it would be advantageous to propagate onto the private processor bus only those invalidates corresponding to memory addresses resident in that processor's cache.